import os
import time
import threading

import numpy as np
from snakeLogit import DirectedPosition, Position

def checkCanReachFood(snake, direction_):
    """
    Check whether the current head can reach the food? If it can reach the food, find the shortest path
    to the food and return the next direction.
    """
    def printVisitedMap(visited):
        matrix = [[0 for i in range(snake.cols)] for j in range(snake.rows)]
        for pos in visited:
            matrix[pos.x][pos.y] = 1
        for i, body in enumerate(snake.snake_body):
            if i == 0:
                matrix[body.x][body.y] = 2
            else:
                matrix[body.x][body.y] = 3
        
        for i in range(snake.rows):
            for j in range(snake.cols):
                print(matrix[i][j], end='')
            print('')

    def canReachFood(direction_):
        next_position = snake.snake_body[0].next(snake.directions[direction_])
        visited_set = set()
        visited_set.add(next_position)
        queue = [next_position]
        while len(queue):
            cur_position = queue[0]
            queue.pop(0)
            for d in snake.directions:
                new_position = cur_position.next(d)
                if new_position in snake.snake_body or new_position in visited_set or \
                    new_position.x < 0 or new_position.x >= snake.rows or \
                    new_position.y < 0 or new_position.y >= snake.cols:
                    continue
                if new_position == snake.food_position:
                    visited_set.add(new_position)
                    if len(visited_set) > 2 * len(snake.snake_body) / 3:
                        # print("CheckCanReachFood detection: success to reach food")
                        # printVisitedMap(visited_set)
                        # print('True', -1)
                        return (True, -1)
                    else:
                        # print("CheckCanReachFood detection: space not enough")
                        # printVisitedMap(visited_set)
                        # print('False', len(visited_set))
                        # time.sleep(1)
                        return (False, len(visited_set))
                queue.append(new_position)
                visited_set.add(new_position)
        # printVisitedMap(visited_set)
        # print("CheckCanReachFood detection: can not reach food.")
        # print('False', len(visited_set))
        # time.sleep(1)
        return (False, len(visited_set))

    return canReachFood(direction_)

def emergencyAvoidance(snake, illegal_direction_list = []):
    """Emergency avoidance"""
    
    def collisionDetect(direction_):
        """
        Collision detector in the given direction
        @return: True if has collision
        """
        next_position = snake.snake_body[0].next(snake.directions[direction_])
        if next_position in snake.snake_body:
            return True
        if next_position.x < 0 or next_position.x >= snake.rows:
            return True
        if next_position.y < 0 or next_position.y >= snake.cols:
            return True
        return False


    if not collisionDetect(snake.getCurrentDirection()):
        return -1
    else:
        best_cho, max_space = -2, -2
        for i in range(4):
            if abs(i - snake.getCurrentDirection()) == 2:
                continue
            # if collision will occur, continue
            if collisionDetect(i):
                continue
            # if can reach food position and has enough space for the snake, return.
            check_result = checkCanReachFood(snake, i)
            if check_result[0]:
                return i
            else:
                if check_result[1] > max_space:
                    best_cho, max_space = i, check_result[1]
    return best_cho

def autoPlayGreedy(snake, locker, sleep_time=0.5):
    """Autoplay algorithm with greedy strategy, its the simplest autoplay strategy"""
    instruction_queue = []

    while True:
        if snake.getCurrentStatus() == 'alived':
            # update instruction queue if its empty already.
            if len(instruction_queue) == 0:
                cur_direction = snake.getCurrentDirection()
                food_position = snake.food_position
                head_position = snake.snake_body[0]
                x_bias, y_bias = head_position.x - food_position.x, head_position.y - food_position.y
                # Situation-1
                if x_bias == 0 and y_bias > 0:
                    if cur_direction == 0:
                        if head_position.x == 0:
                            instruction_queue.extend([1, 2, 3, 2])
                        else:
                            instruction_queue.extend([3, 2, 1, 2])
                    elif cur_direction in [1, 3]:
                        instruction_queue.append(2)
                # Situation-2
                elif x_bias == 0 and y_bias < 0:
                    if cur_direction == 2:
                        if head_position.x == 0:
                            instruction_queue.extend([1, 0, 3, 0])
                        else:
                            instruction_queue.extend([3, 0, 1, 0])
                    elif cur_direction in [1, 3]:
                        instruction_queue.append(0)
                # Situtation-3 
                elif y_bias == 0 and x_bias > 0:
                    if cur_direction == 1:
                        if head_position.y == 0:
                            instruction_queue.extend([0, 3, 2, 3])
                        else:
                            instruction_queue.extend([2, 3, 0, 3])
                    elif cur_direction in [0, 2]:
                        instruction_queue.append(3)
                # Situation-4
                elif y_bias == 0 and x_bias < 0:
                    if cur_direction == 3:
                        if head_position.y == 0:
                            instruction_queue.extend([0, 1, 2, 1])
                        else:
                            instruction_queue.extend([2, 1, 0, 1])
                    elif cur_direction in [0, 2]:
                        instruction_queue.append(1)
                # Situation-5
                if x_bias > 0 and y_bias < 0:
                    if cur_direction == 1:
                        instruction_queue.append(0)
                    elif cur_direction == 2:
                        instruction_queue.append(3)
                # Situtation-6
                if x_bias > 0 and y_bias > 0:
                    if cur_direction == 0:
                        instruction_queue.append(3)
                    elif cur_direction == 1:
                        instruction_queue.append(2)
                # Situation-7
                if x_bias < 0 and y_bias < 0:
                    if cur_direction == 2:
                        instruction_queue.append(1)
                    elif cur_direction == 3:
                        instruction_queue.append(0)
                # Situation-8
                if x_bias < 0 and y_bias > 0:
                    if cur_direction == 0:
                        instruction_queue.append(1)
                    elif cur_direction == 3:
                        instruction_queue.append(2)
             
            locker.acquire()
            # print("SnakeDirection acquire lock.")

            if len(instruction_queue) != 0:
                instruction = instruction_queue[0]
                instruction_queue.pop(0)
                pre_direction = snake.getCurrentDirection()
                snake.setCurrentDirection(instruction)
                emergency_check_result = emergencyAvoidance(snake)
                # if its safe in current instruction.
                if emergency_check_result == -1:
                    pass
                # if its dangerous in current instruction.
                elif emergency_check_result == -2:
                    instruction_queue.append(instruction)
                    snake.setCurrentDirection(pre_direction)
                    emergency_check_result_2 = emergencyAvoidance(snake, [instruction])
                    if emergency_check_result_2 == -1:
                        pass
                    elif emergency_check_result_2 == -1:
                        print("[1] No solution.")
                    else:
                        snake.setCurrentDirection(emergency_check_result_2)
                else:
                    snake.setCurrentDirection(emergency_check_result)
            else:
                emergency_check_result = emergencyAvoidance(snake)
                if emergency_check_result == -1:
                    pass
                elif emergency_check_result == -2:
                    print("[2] No solution")
                else:
                    snake.setCurrentDirection(emergency_check_result)
                
            # print("SnakeDirection release lock.")
            locker.release()
        
        time.sleep(sleep_time)

def autoplayBFS(snake, locker, sleep_time=0.5):
    """Autoplay algorithm implemented by bfs."""

    def canReachFood():
        cur_position = DirectedPosition(snake.snake_body[0], Position(-1, -1))
        visited_set = set()
        visited_set.add(cur_position)
        queue = [cur_position]
        while len(queue):
            cur_position = queue[0]
            queue.pop(0)
            for d in snake.directions:
                new_position = cur_position.next(d)
                if new_position.pos in snake.snake_body or new_position in visited_set or \
                    new_position.pos.x < 0 or new_position.pos.x >= snake.rows or \
                    new_position.pos.y < 0 or new_position.pos.y >= snake.cols:
                    continue
                # If already reach the food position.
                if new_position.pos == snake.food_position:
                    visited_set.add(new_position)
                    return (True, list(visited_set))

                queue.append(new_position)
                visited_set.add(new_position)
        return (False, None)

    def getNextDirection(visited_set):
        cur_position = Position(-1, -1)
        parent_position = snake.food_position
        while parent_position != snake.snake_body[0]:
            for position in visited_set:
                if position.pos == parent_position:
                    cur_position, parent_position = position.pos, position.parent_pos
                    visited_set.remove(position)
                    break

        if cur_position.x == snake.snake_body[0].x and cur_position.y > snake.snake_body[0].y:
            return 0
        if cur_position.y == snake.snake_body[0].y and cur_position.x > snake.snake_body[0].x:
            return 1
        if cur_position.x == snake.snake_body[0].x and cur_position.y < snake.snake_body[0].y:
            return 2
        if cur_position.y == snake.snake_body[0].y and cur_position.x < snake.snake_body[0].x:
            return 3
        
        return 0

    while True:
        if snake.getCurrentStatus() == 'alived':
            locker.acquire()
            search_result = canReachFood()
            if search_result[0]:
                new_direction = getNextDirection(search_result[1])
                # print("Update new direction to:", new_direction)
                snake.setCurrentDirection(new_direction)
            else:
                print("Emergency avoidance occured!")
                new_direction = emergencyAvoidance(snake)
                if new_direction >= 0:
                    snake.setCurrentDirection(new_direction)
            locker.release()

        time.sleep(sleep_time)

def autoplayBFSPlus(snake, locker, sleep_time=0.5):
    """Wonderful version of snakeAI based on BFS strategy."""

    def canReachTarget(target):
        # If the snake_head is just aside the snake_tail, return False to avoid self-collision.
        if target == snake.snake_body[-1] and \
           abs(snake.snake_body[0].x - snake.snake_body[-1].x) + abs(snake.snake_body[0].y - snake.snake_body[-1].y) == 1:
            return (False, -1)
        cur_position = DirectedPosition(snake.snake_body[0], Position(-1, -1))
        visited_set = set()
        visited_set.add(cur_position)
        queue = [cur_position]
        while len(queue):
            cur_position = queue[0]
            queue.pop(0)
            for d in snake.directions:
                new_position = cur_position.next(d)

                # If already reach the target position.
                if new_position.pos == target:
                    visited_set.add(new_position)
                    return (True, list(visited_set))

                if new_position.pos in snake.snake_body or new_position in visited_set or \
                    new_position.pos.x < 0 or new_position.pos.x >= snake.rows or \
                    new_position.pos.y < 0 or new_position.pos.y >= snake.cols:
                    continue

                queue.append(new_position)
                visited_set.add(new_position)
        return (False, None)

    def getNextDirection(visited_set, target):
        cur_position = Position(-1, -1)
        parent_position = target
        while parent_position != snake.snake_body[0]:
            for position in visited_set:
                if position.pos == parent_position:
                    cur_position, parent_position = position.pos, position.parent_pos
                    visited_set.remove(position)
                    break

        if cur_position.x == snake.snake_body[0].x and cur_position.y > snake.snake_body[0].y:
            return 0
        if cur_position.y == snake.snake_body[0].y and cur_position.x > snake.snake_body[0].x:
            return 1
        if cur_position.x == snake.snake_body[0].x and cur_position.y < snake.snake_body[0].y:
            return 2
        if cur_position.y == snake.snake_body[0].y and cur_position.x < snake.snake_body[0].x:
            return 3
        
        return 0

    def checkCanEatTheFood():
        """Do the simulated scrawling."""
        original_snake_body = snake.snake_body[:]
        original_direction = snake.getCurrentDirection()

        while snake.snake_body[0] != snake.food_position:
            search_result = canReachTarget(snake.food_position)
            if search_result[0]:
                new_direction = getNextDirection(search_result[1], snake.food_position)
                snake.setCurrentDirection(new_direction)
                snake.forward(simulation=True)
            else:
                new_direction = emergencyAvoidance(snake)
                if new_direction >= 0:
                    snake.setCurrentDirection(new_direction)
                    snake.forward(simulation=True)


        ret = canReachTarget(snake.snake_body[-1])[0]
        snake.snake_body = original_snake_body
        snake.setCurrentDirection(original_direction)

        return ret

    while True:
        if snake.getCurrentStatus() == 'alived':
            locker.acquire()
            search_food_result = canReachTarget(snake.food_position)
            forbidden_direction = []
            # If currently can reach the food.
            if search_food_result[0]:
                # Do the simulation scrawling and check whether the snake can find its tail.
                # If it can find its tail, do not eat the food and follow its tail this time,
                # otherwise eat the food.
                can_eat_the_food = checkCanEatTheFood()
                if can_eat_the_food:
                    new_direction = getNextDirection(search_food_result[1], snake.food_position)
                    snake.setCurrentDirection(new_direction)
                else:
                    can_reach_tail = canReachTarget(snake.snake_body[-1])
                    # If can reach tail, follow its tail this time.
                    if can_reach_tail[0]:
                        new_direction = getNextDirection(can_reach_tail[1], snake.snake_body[-1])
                        snake.setCurrentDirection(new_direction)
                    # Otherwise, emergency avoidance
                    else:
                        # print("Emergency avoidance occured!")
                        new_direction = emergencyAvoidance(snake)
                        if new_direction >= 0:
                            snake.setCurrentDirection(new_direction)
            # If cannot reach the food, try to follow its tail.
            else:
                can_reach_tail = canReachTarget(snake.snake_body[-1])
                # If can reach tail, follow its tail this time.
                if can_reach_tail[0]:
                    new_direction = getNextDirection(can_reach_tail[1], snake.snake_body[-1])
                    snake.setCurrentDirection(new_direction)
                # Otherwise, emergency avoidance
                else:
                    # print("Emergency avoidance occured!")
                    new_direction = emergencyAvoidance(snake)
                    if new_direction >= 0:
                        snake.setCurrentDirection(new_direction)
            locker.release()

        time.sleep(sleep_time)


def autoPlayRL(snake, sleep_time=0.5):
    """Autoplay algorithm implemented by reinforce learning strategy Q-Learning. This is just an attemp."""
    q_table_path = './q_table.csv'
    if not os.path.exists(q_table_path):
        # q_table = np.array(4 * )
        pass